Octree

Construction

Cconstruction(root)=Cintersection+8â‹…Cconstruction(subtree)C_{construction}(root) = C_{intersection} + 8 \cdot C_{construction}(subtree)

Cintersection=CSAT+Cfully insideC_{intersection} = C_{SAT} + C_{fully \space inside} early out if SAT fails, but little gains (SAT is way the most complex part by far)

Cfully inside=8⋅COBBC_{fully \space inside} = 8 \cdot C_{OBB} check AABB for OBB: we check if all the vertices of the AABB are inside the OBB of the region

CSAT=9â‹…xv+(6+6+9)â‹…[(8+8)â‹…(dotv+2â‹…cmpf)]C_{SAT} = 9 \cdot x_v + (6+6+9) \cdot [(8+8) \cdot (dot_v + 2 \cdot cmp_f)] approximate cost and many early outs

Traversal

Clookup=levelsâ‹…[3â‹…(mulf+cmpf)]C_{lookup} = levels \cdot [3 \cdot (mul_f + cmp_f)] for each axis we have to get if the component is before or after the half point

AABB for OBB

Construction

Cconstruction=(3â‹…Vâ‹…BVHs)â‹…CinsideC_{construction} = (3 \cdot V \cdot BVHs) \cdot C_{inside}

Cinside=CAABB+COBBC_{inside} = C_{AABB} + C_{OBB} early out if the AABB part fails

CAABB=6â‹…cmpfC_{AABB} = 6 \cdot cmp_f early out when one component doesn't satisfy the comparison (outside AABB)

COBB=addv+3â‹…(absv+dotv+cmpf)C_{OBB} = add_v + 3 \cdot (abs_v + dot_v + cmp_f) there may be an early out if the first (or second) coordinate is already out of the OOBB

Traversal

Ctraversal=BVHsâ‹…CinsideC_{traversal} = BVHs \cdot C_{inside}

Simplify to AABBs